package 热题100;

public class 热题33搜索旋转排序数组 {

    public static void main(String[] args) {
        int[] arr = {6,0,1,2,3};
        热题33搜索旋转排序数组 o = new 热题33搜索旋转排序数组();
        System.out.println(o.search(arr, 5));
    }


    /*
    思路：
    1，先找到旋转节点得位置
    2,在找到旋转节点之前和旋转之后得位置进行二叉查找
     */
    public int search(int[] nums, int target) {
        //找到反转点
        int point = searchByBN(nums, 0, nums.length - 1);

        //找到目标target值
        int i = -1;
        //如果target在反转点得右侧
        if (target < nums[nums.length-1]){
            i = help(nums,point,nums.length-1,target);
            //target在反转点得左侧
        }else if (target > nums[nums.length-1]){
            i = help(nums,0,point,target);
            //如果target就是最后一个数，返回最后一个数
        }else {
            return nums.length-1;
        }
        //找到目标位置，返回下标
        return i;
    }

    private int help(int[] arr, int i, int j,int target) {
        //如果传入得范围只有一个数，并且这个数还不相等，直接返回-1
        if (i == j && arr[i] != target){
            return -1;
        }
        //如果传入得范围左右边界刚好等于target，直接返回i，或j
        if (arr[i] == target){
            return i;
        }
        if (arr[j] == target){
            return j;
        }

        //否则使用中间下标，进行二分查找
        int l = i,r = j;
        int mid = (l + r) >> 1;
        //中间值等于target，找到target返回
        if (arr[mid] == target){
            return mid;
            //中间值小，向有寻找
        }else if (arr[mid] < target){
            return help(arr,mid+1,r,target);
            //中间值大，向右寻找
        }else {
            return help(arr,l,mid,target);
        }
    }

    public int searchByBN(int[] arr,int i,int j){
        //找中间反转点
        if (i == j){
            return i;
        }

        int mid = (i + j) >> 1;

        //反转点在左边
        if (arr[mid] < arr[j]){
            return searchByBN(arr,i,mid);
            //反转点在右边
        }else if (arr[mid] > arr[j]){
            return searchByBN(arr,mid+1,j);
            //找到反转点，返回mid
        }else {
            return mid;
        }
    }

}
